Раскраска графа и хроматическое число

Множество вершин графа называется **независимым**, если никакая пара вершин из данного множества не является смежной в графе. $\beta(G)$ — количество вершин в наибольшем по мощности независимом множестве (**число независимости**).

Пусть $k \in \mathbb{N}$, **раскраской** графа $G = (V,E)$ называется функция $f \colon V \to \{1, \dots, k\}$, причем если $f(v) = i$, то говорят, что $i$ — цвет вершины $v$. Раскраска называется **правильной**, если никакие две вершины одного цвета не смежны. Множества вершин, раскрашенных в один цвет, являются независимыми.

$\chi(G)$ — наименьшее число цветов, для которого есть правильная раскраска графа $G$

$\chi(G) = 1 \iff$ в $G$ нет ребер. $\chi(G) = 2 \iff G$ двудольный (хотя бы с одним ребром). Двудольный граф по определению разбивается на два независимых множества. $\chi(K_n) = n$. Все вершины полного графа должны иметь разные цвета. $\chi(C_n) = 2 + n \mod 2$. Четный цикл — двудольный граф, нечетный превращается в двудольный удалением вершины.